/*
题目链接：https://leetcode.cn/problems/minimum-time-to-complete-trips/submissions/571971076/
题目：2187.完成旅途的最少时间
彭珵
提交时间：2024.9.22
二分，最少时间
*/

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        // 定义一个 lambda 函数 f，输入时间 t，返回能够完成的旅途数
        auto f = [&] (long long t)-> long long {
            long long cnt = 0; // 初始化计数器
            for(int i = 0; i < time.size(); i++) {
                cnt += t / time[i]; // 计算在时间 t 内每个旅行的完成次数
            }
            return cnt; // 返回总的完成旅途数
        };

        int n = time.size(); // 获取旅行数量
        long long min_t = *min_element(time.begin(), time.end()); // 找到最小旅行时间
        long long max_t = *max_element(time.begin(), time.end()); // 找到最大旅行时间
        long long l = min_t; // 二分搜索的左边界
        long long r = max_t * totalTrips; // 二分搜索的右边界，最大可能时间

        while(l <= r) { // 当左边界小于等于右边界时继续搜索
            long long mid = l + (r - l) / 2; // 计算中间值
            if(f(mid) >= (long long)totalTrips) { // 如果在 mid 时间内能完成的旅途数大于等于总旅途数
                r = mid - 1; // 则尝试更小的时间
            } else { // 如果完成的旅途数少于总旅途数
                l = mid + 1; // 则尝试更大的时间
            }
        }
        return r + 1; // 返回最小时间，r + 1 是因为 r 是最后一个不满足条件的值
    }
};